package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.ArrayProblem;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * see
 * 136. Single Number
 * 268. Missing Number
 * 41. First Missing Positive
 * 287. Find the Duplicate Number
 * <p>
 * 对于这种题, 给极端条件, 一般都得借助数学了: 求和sum, 求乘积, 异或
 * <p>
 * - 有个用数组里的数, 当下一个节点的index, 把数组链起来, LC297
 * - 当长度为n的数组里, 都是小于n的int时, 可以考虑这个方法
 * - 不能排序, nlogn超时了
 * - 41. First Missing Positive
 *
 * <p>
 * - bitmap这种方法, 占空间
 * - 前两个高赞的, 用负号和余数标记哪个index没有被标记过, 就是缺少的数, 牛逼啊.
 * - 我写的这个方法, 和另一个高赞的"Simple Java In-place sort solution"是一个思路, 链表数组法.
 * <p>
 * https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/
 * without extra space and in O(n) runtime
 *
 * @author tzp
 * @since 2020/10/15
 */
public class LC448 implements ArrayProblem {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]) {
                swap(nums, i, nums[i] - 1);
            }
        }
        List<Integer> r = new ArrayList<>();
        System.out.println(Arrays.toString(nums));
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) r.add(i + 1);
        }
        return r;
    }

    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public static void main(String[] args) {
        System.out.println(new LC448()
                .findDisappearedNumbers(new int[]{4, 3, 2, 7, 8, 2, 3, 1}));
    }
}
